import math
from collections import deque
import urllib2

script = urllib2.urlopen("https://creator-dev.googlecode.com/svn/trunk/scripts/mgcoord3d.py")
exec(script.read())
script.close()

def make_bounding_box(poly_list):
	box = None
	for poly in poly_list:
		vertex = mgGetChild(poly)
		while vertex:
			ok, x, y, z = mgGetVtxCoord(vertex)
			pt = mgMakeCoord3d(x, y, z)
			if box == None:
				box = mgMakeBox(pt, pt)
			else:
				mgBoxExpandCoord3d(box, pt)
			vertex = mgGetNext(vertex)
	return box
	
def compute_mean(pt_list):
	mean = None
	if pt_list:
		sum = reduce(lambda x, y: x + y, pt_list)
		mean = mgCoord3dDivide(sum, len(pt_list))
	return mean
	
def compute_absolute_deviation(pt_list, m):
	abs_dev = None
	if pt_list:
		abs_dev = mgCoord3dZero()
		for pt in pt_list:
			abs_dev.x += math.fabs(pt.x - m.x)
			abs_dev.y += math.fabs(pt.y - m.y)
			abs_dev.z += math.fabs(pt.z - m.z)
	return abs_dev
		
def compute_centroid(poly):
	pt_list = []
	vertex = mgGetChild(poly)
	while vertex:
		ok, x, y, z = mgGetVtxCoord(vertex)
		pt_list.append(mgMakeCoord3d(x, y, z))
		vertex = mgGetNext(vertex)
	return compute_mean(pt_list)

def get_max_component_index(pt):
	if pt.x >= pt.y and pt.x >= pt.z:
		return 0
	if pt.y >= pt.x and pt.y >= pt.z:
		return 1
	if pt.z >= pt.x and pt.z >= pt.x:
		return 2

class bbt:
	root = None
	adj_list = {}
	leaf_to_poly = {}
	ignore_func = None
	ignore_func_arg = None
	iterator_depth = -1
	
	def split_bounding_box(self, bounding_box):
		poly_list = self.adj_list[bounding_box][0]
		poly_list_length = len(poly_list)
		if (poly_list_length == 1):
			self.leaf_to_poly[bounding_box] = poly_list[0]
			self.adj_list[bounding_box] = []
		elif (poly_list_length > 1):
			centroid_list = self.adj_list[bounding_box][1]
			centroid_mean = compute_mean(centroid_list)
			centroid_abs_dev = compute_absolute_deviation(centroid_list, centroid_mean)
			max_abs_dev_index = get_max_component_index(centroid_abs_dev)
			poly_sublist_high = []
			centroid_sublist_high = []
			poly_sublist_low = []
			centroid_sublist_low = []
			for i in range(poly_list_length):
				poly = poly_list[i]
				centroid = centroid_list[i]
				centroid_comp = centroid[max_abs_dev_index]
				centroid_mean_comp = centroid_mean[max_abs_dev_index]
				if math.fabs(centroid_comp - centroid_mean_comp) <= 0.0001:
					if len(poly_sublist_high) < len(poly_sublist_low):
						poly_sublist_high.append(poly)
						centroid_sublist_high.append(centroid)
					else:
						poly_sublist_low.append(poly)
						centroid_sublist_low.append(centroid)
				elif centroid_comp > centroid_mean_comp:
					poly_sublist_high.append(poly)
					centroid_sublist_high.append(centroid)
				else:
					poly_sublist_low.append(poly)
					centroid_sublist_low.append(centroid)
			bounding_box_high = make_bounding_box(poly_sublist_high)
			bounding_box_low = make_bounding_box(poly_sublist_low)
			self.adj_list[bounding_box_high] = [poly_sublist_high, centroid_sublist_high]
			self.adj_list[bounding_box_low] = [poly_sublist_low, centroid_sublist_low]
			self.adj_list[bounding_box] = [bounding_box_high, bounding_box_low]
			self.split_bounding_box(bounding_box_high)
			self.split_bounding_box(bounding_box_low)
	__split_bounding_box = split_bounding_box
	
	def __init__(self, poly_list = None):
		if poly_list:
			centroid_list = []
			for poly in poly_list:
				centroid = compute_centroid(poly)
				if centroid:
					centroid_list.append(centroid)
				else:
					print "error: failed to compute the centroid of " + mgGetName(poly)
					return
			bounding_box = make_bounding_box(poly_list)
			self.root = bounding_box
			self.adj_list = {bounding_box : [poly_list, centroid_list]}
			self.__split_bounding_box(bounding_box)
			
	def __iter__(self):
		if self.root:
			# make a queue consisted of ordered pairs of the form (box, depth) to enable breadth first search
			self.queue = deque()
			if not (self.ignore_func and self.ignore_func(self.root, self.ignore_func_arg)):
				self.queue.append((self.root, 0))
		return self

	def next(self):
		if self.queue:
			head = self.queue.popleft()
			child_list = self.adj_list[head[0]]
			for box in child_list:
				if not (self.ignore_func and self.ignore_func(box, self.ignore_func_arg)):
					self.queue.append((box, head[1] + 1))
			self.iterator_depth = head[1]
			return head[0]
		else:
			self.iterator_depth = -1
			raise StopIteration

	def get_poly(self, box):
		return self.leaf_to_poly.get(box)
